A set $C \subseteq N$ is a cover if  $\sum_{j \in C} a_j >  b$. A cover is \textit{minimal} if $C \setminus \{j\}$ is not a cover for any $j \in C$.

\textbf{Note:} C is a cover if and only if its associated incidence vector $\textbf{x}^C$ is infeasible for X. \footnote{Lecture slides p. 212}

\medskip

$C = \{3,4,5\}$ is a \textit{minimal} cover for $X$, as $a_3+a_4+a_5=7+5+5 > 14$ and $a_3+a_4+a_5-a_i \leq 14, i \in \{3,4,5\}$.

The associated minimal cover inequality CI is

$$x_3+x_4+x_5 \leq |C| - 1 = 2.$$

The algorithm from the lecture\footnote{Lecture slides p. 219} for lifting the coefficients consists of solving the following ILP $|N \setminus C|$ times to yield the coefficients $\alpha_{j_t} = |C|-1-\zeta_t$. $j_1,...,j_r$ is an ordering of $N \setminus C$.

\begin{align*}
\zeta_t = \max \quad \sum_{i=1}^{t-1} \alpha_{j_i} x_{j_i} + \sum_{j \in C} x_j & \\
\textrm{s.t.} \quad \sum_{i=1}^{t-1} a_{j_i} x_{j_i} + \sum_{j \in C} a_j x_j & \leq b - a_{j_t} \\
\vc{x} & \in \{0,1\}^{|C|+t-1} \\
\end{align*}

We have $r=3$ and $(j_1,j_2,j_3)=(1,2,6)$, and this leads to 3 iterations of solving the ILP.

\begin{align*}
\zeta_1 = \max \quad x_3+x_4+x_5 & \\
\textrm{s.t.} \quad 7x_3+5x_4+5x_5 & \leq 2 \\
\end{align*}
It follows that $\zeta_1 = 0$ and $\alpha_1 = 2.$

\begin{align*}
\zeta_2 = \max \quad 2x_1+x_3+x_4+x_5 & \\
\textrm{s.t.} \quad 12x_1+7x_3+5x_4+5x_5 & \leq 5 \\
\end{align*}
It follows that $\zeta_2 = 1$ and $\alpha_2 = 1.$

\begin{align*}
\zeta_3 = \max \quad 2x_1+x_2+x_3+x_4+x_5 & \\
\textrm{s.t.} \quad 12x_1+9x_2+7x_3+5x_4+5x_5 & \leq 11 \\
\end{align*}
It follows that $\zeta_3 = 2$ and $\alpha_6 = 0.$

\medskip

This yields the strong valid inequality $2x_1+x_2+x_3+x_4+x_5 \leq 2.$